#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 1000000  
struct header
{
    int size;   // including the size of the header.
    bool empty_flag;
}*first;
// Assume to allocate these MAX_SIZE bytes.
char buf[MAX_SIZE];

int my_allocate(int size);
bool my_free(int ptr);

int my_allocate(int size)
{
    int s = size + sizeof(header);
    for (char *i = (char*)first; i - buf < MAX_SIZE; i += ((header*)i)->size)
    {
        header *hi = (header*)i;
        if (hi->empty_flag)
        {
            // Trying to merge.
            for (char *j = i + hi->size; j - buf < MAX_SIZE; j += ((header*)j)->size)
            {
                if (((header*)j)->empty_flag)
                    hi->size += ((header*)j)->size;
                else
                    break;
            }
            if (hi->size >= s)
            {
                // Allocate succeed.
                hi->empty_flag = false;
                if (s + sizeof(header) < hi->size)
                {
                    // Split.
                    header *hj = (header*)(i + s);
                    hj->size = hi->size - s;
                    hj->empty_flag = true;
                    hi->size = s;
                }
                return i + sizeof(header) - buf;
            }
        }
    }
    return -1;
}

bool my_free(int ptr)
{
    header *i = (header*)(buf + ptr) - 1;
    if (!i->empty_flag)
    {
        i->empty_flag = true;
        return true;
    }
    else
        return false;
}

int main()
{
    // initialization.
    first = (header*)buf;
    first->size = sizeof(buf);
    first->empty_flag = true;
    
    while(1)
    {
        int opt;
        printf("Please enter the operation: 1. allocate 2. free\n");
        scanf("%d",&opt);
        if (opt == 1)
        {
            printf("Please enter the size you want: ");
            scanf("%d", &opt);
            int ans = my_allocate(opt);
            if (ans < 0)
                printf("Allocate failed.\n");
            else
                printf("Addresses from %d to %d is allocated.\n", ans, ans + opt);
        }
        else
        {
            printf("Please enter the starting address of the block you want to free: ");
            scanf("%d", &opt);
            if (my_free(opt))
                printf("Free succeed.\n");
            else
                printf("Free failed.\n");
        }
    }
}
